package ai.zixing.mashibing.basic_class.class09;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

/**
 * 给定一个由字符串组成的数组strs，
 * 必须把所有的字符串拼接起来，
 * 返回所有可能的拼接结果中，字典序最小的结果
 */
public class Code01_LowestLexicography {

    // 全排列方式
    public static String lowestString1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        ArrayList<String> all = new ArrayList<>();
        HashSet<Integer> use = new HashSet<>();
        process(strs, use, "", all);
        String lowest = all.get(0);
        for (int i = 1; i < all.size(); i++) {
            if (all.get(i).compareTo(lowest) < 0) {
                lowest = all.get(i);
            }
        }
        return lowest;
    }

    // strs 存放所有字符串
    // 已经使用过的字符串的下标，在 use 中登记，不要再使用了
    // 已经使用过的字符串，拼接成了 path
    // 用 all 收集所有可能拼接的字符串
    public static void process(String[] strs, HashSet<Integer> use, String path, ArrayList<String> all) {
        // 所有字符串都使用了
        if (use.size() == strs.length) {
            all.add(path);
        } else {
            // 遍历所有字符串拼接
            for (int i = 0; i < strs.length; i++) {
                if (!use.contains(i)) {
                    // 深度优先遍历的常用套路，构成全排列
                    // 先标记为使用
                    use.add(i);
                    process(strs, use, path + strs[i], all);
                    // 使用完之后需要回退到使用前，去【递归】遍历下一个
                    use.remove(i);
                }
            }
        }
    }

    public static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);
        }
    }

    public static String lowestString2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, new MyComparator());
        String res = "";
        for (int i = 0; i < strs.length; i++) {
            res += strs[i];
        }
        return res;
    }


    public static String generateRandomString(int strLen) {
        // + 1 保证生成的字符串不为 ""
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 5);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen)];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    public static String[] copyStringArray(String[] arr) {
        String[] ans = new String[arr.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

    public static void printArray(String[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int arrLen = 6;
        int strLen = 5;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr1 = generateRandomStringArray(arrLen, strLen);
            String[] arr2 = copyStringArray(arr1);
            if (!lowestString1(arr1).equals(lowestString2(arr2))) {
                System.out.println("Oops!");
                printArray(arr1);
                System.out.println(lowestString1(arr1));
                printArray(arr2);
                System.out.println(lowestString2(arr2));
            }
        }
        System.out.println("finish!");
    }
}
